#include <stdio.h>
#include <string.h>
#include <stdlib.h>


	const long MAXN=501;
	long	map[MAXN][MAXN];
	long	n;
	long	maxlen;
	long	Ncase;


#define max(a,b) (((a)>(b))?(a):(b))
main()
{
	long	i,j,k,t;

	//freopen("highways.in","r",stdin);


	scanf("%ld",&Ncase);
	while (Ncase-->0)
	{
		scanf("%ld",&n);
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
			{
				scanf("%ld",&(map[i][j]));
			}
		for (k=1;k<=n;k++)
			for (i=1;i<=n;i++)
				if (i!=k)
					for (j=i+1;j<=n;j++)
						if (j!=i && j!=k)
						{
							t=max(map[i][k],map[k][j]);
							if (t<map[i][j])
							{
								map[j][i]=map[i][j]=t;
								//if (map[i][k]<maxlen) maxlen=map[i][k];
							}
						}
		maxlen=0;
		for (i=1;i<=n;i++)
			for (j=i+1;j<=n;j++)
				if (map[i][j]>maxlen) maxlen=map[i][j];
		printf("%ld\n",maxlen);
	}
	return 0;
}














